public class Test {
    public static SingleLinkedList.ListNode getIntersectionNode
            (SingleLinkedList.ListNode headA,SingleLinkedList.ListNode headB){
        //1.假设A链表长
        SingleLinkedList.ListNode pl = headA;
        SingleLinkedList.ListNode ps = headB;
        int lenA = 0;
        int lenB = 0;

        while (pl != null){
            lenA++;
            pl = pl.next;
        }
        while (ps != null){
            lenB++;
            ps = ps.next;
        }
        //归位
        pl = headA;
        ps = headB;

        int len = lenA - lenB;

        //2.判断len是正数还是负数；
        if(len < 0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }

        //3.长链表pl走差值len步
        while (len != 0){
            pl = pl.next;
            len--;
        }

        //4.一直走，知道双指针相遇
        while(pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == null){
            return null;
        }
        return pl;
    }

    public static void creatCut(SingleLinkedList.ListNode headA,
                                SingleLinkedList.ListNode headB){
        headA.next.next.next = headB.next.next.next;
    }

    public static void main(String[] args) {
        SingleLinkedList list1 = new SingleLinkedList();
        SingleLinkedList list2 = new SingleLinkedList();
        list1.addLast(23);
        list1.addLast(34);
        list1.addLast(45);
        list1.addLast(56);


        list2.addLast(15);
        list2.addLast(26);
        list2.addLast(33);
        list2.addLast(25);
        list2.addLast(87);
        list2.addLast(29);

        creatCut(list1.head,list2.head);

        SingleLinkedList.ListNode ret = getIntersectionNode(list1.head,list2.head);
        System.out.println(ret.val);
    }

    public static void main1(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        list.addLast(4);
        list.addLast(5);
        list.addLast(6);
        list.display();
        System.out.println("=======");
        list.addIndex(4,45);
        list.display();
        System.out.println("=======");
        list.removeAllKey(4);
        list.display();
    }
}

